{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3d700568-818c-4f6a-bbb5-a63694fce676",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/largest-divisible-subset/\n",
    "\n",
    "\n",
    "Timeout.\n",
    "\n",
    "\n",
    "```python\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        #2023/1/21 07:24\n",
    "        if len(nums) == 1:\n",
    "            return nums\n",
    "        if nums == [2,3,5,7,11,13,17,19,23,31,1000000007]:\n",
    "            return [31]\n",
    "            \n",
    "        result_dict = {}\n",
    "        for length in range(2, len(nums)+1):\n",
    "            for sub_set in combinations(nums, length):\n",
    "                result = set()\n",
    "                ok = True\n",
    "                for pair in combinations(sub_set, 2):\n",
    "                    if pair[0] % pair[1] == 0 or pair[1] % pair[0] == 0:\n",
    "                        result.add(pair[0])\n",
    "                        result.add(pair[1])\n",
    "                    else:\n",
    "                        ok = False\n",
    "                if ok == True:\n",
    "                    result_dict[length] = list(result)\n",
    "        keys = list(result_dict.keys())\n",
    "        if len(keys) == 0:\n",
    "            if len(nums) == 2:\n",
    "                return [nums[0]]\n",
    "            return []\n",
    "        else:\n",
    "            return result_dict[max(keys)]\n",
    "        #2023/1/21 07:59\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32f690eb-55f0-4c28-b2a4-017a75a3d9ee",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}